procedure convexHull(); // n - pt count; a - array of pt; b - array of pt in convex hull; k - pt in convex hull count
 
	function cw(a, b, c : pt) : boolean;
	begin
		result := a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
	end;
 
	function ccw(a, b, c : pt) : boolean;
	begin
		result := a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
	end; 
 
	procedure sort(l, r : longint);
 
	var
		i, j : longint;
		x, y : pt;
 
	begin
		i := l;
		j := r;
		x := a[l + random(r - l + 1)];
		repeat
			while (a[i].x < x.x) or ((a[i].x = x.x) and (a[i].y < x.y)) do inc(i);
			while (a[j].x > x.x) or ((a[j].x = x.x) and (a[j].y > x.y)) do dec(j);
			if i <= j then begin
				y := a[i];
				a[i] := a[j];
				a[j] := y;
				inc(i);
				dec(j);
			end;
		until i > j;
		if l < j then sort(l, j);
		if i < r then sort(i, r);
	end;
 
var
	u, d, i : longint;
	p1, p2 : pt;
	up, down : array[0..20010] of pt;
 
begin
	if n = 1 then begin
		k := 1;
		b[1] := a[1];
		exit;
	end;
	sort(1, n);
	p1 := a[1];
	p2 := a[n];
	u := 1;
	d := 1;
	up[1] := p1;
	down[1] := p1;
	for i := 1 to n do begin
		if (i = n) or cw(p1, a[i], p2) then begin
			while (u >= 2) and (not cw(up[u - 1], up[u], a[i])) do dec(u);
			inc(u);
			up[u] := a[i];
		end;
		if (i = n) or ccw(p1, a[i], p2) then begin
			while (d >= 2) and (not ccw(down[d - 1], down[d], a[i])) do dec(d);
			inc(d);
			down[d] := a[i];
		end;
	end;		
	k := 0;
	for i := 1 to u do begin
		inc(k);
		b[k] := up[i];
	end;
	for i := d - 1 downto 1 do begin
		inc(k);
		b[k] := down[i];
	end;
end;